package 面试超级高频;

import MyUtils.MHUtils;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

import static MyUtils.MHUtils.*;
import static MyUtils.MHMoban.*;
/*
    每个节点只处理自己（单cur思想）
    做完题一定写入表格
*/
/*
    key不是node的地址，而是又一个标记值（本题k，v是2个独立标记值
*/
public class LRU缓存淘汰机制146 {
    //链表k-v
    class DoubleNode{
        int key,val;
        DoubleNode prep,next;
        DoubleNode(int k,int v){
            key=k; val=v;
        }
    }
    class LRUCache {
        //map k-node
        Map<Integer, DoubleNode> map = new HashMap<>();
        //2个dm(注意h是dm1.n t是dm2.pre
        DoubleNode dm1, dm2;
        //链表工具里先curS--，老忘
        int curSize=0;
        int maxSize;
        public LRUCache(int maxSize) {
            this.maxSize=maxSize;
            dm1 =new DoubleNode(-1,-1);
            dm2 =new DoubleNode(-1,-1);
            dm1.next= dm2;
            dm2.prep= dm1;
        }

        /**
         * 双向链表工具
         */
        void list_addRight(DoubleNode node){
            curSize++;
            DoubleNode t = dm2.prep;
            //左2
            t.next=node;
            node.prep=t;
            //右2
            node.next=dm2;
            dm2.prep=node;
        }
        void list_delByNode(DoubleNode node){
            curSize--;
            DoubleNode lf = node.prep, rt=node.next;
            lf.next=rt;
            rt.prep=lf;
        }

        /**
         * 题干给的接口[防少：1node2链表3map]
         */
        public void put(int key, int val) {
            //有key不涉及满不满问题
            if(map.containsKey(key)) {
                //key已存在（图的2应该画在1的满里好）
                DoubleNode node = map.get(key);
                list_delByNode(node);
                //加新node，不是老node
                DoubleNode newNode = new DoubleNode(key, val);
//                list_addRight(node);
                list_addRight(newNode);
//                map.put(key,node);
                //这里是新node，val没用呢！
                map.put(key, newNode);
                ptList(dm1);
                return;
            }

            //无key没满
            if(curSize<maxSize){
                DoubleNode node = new DoubleNode(key,val);
                list_addRight(node);
                map.put(key,node);
            }
            //无key满了
            else{
                //删左
                DoubleNode head = dm1.next;
                int head_key = head.key;
                list_delByNode(head);
                map.remove(head_key);
                //插右
                DoubleNode node = new DoubleNode(key, val);
                list_addRight(node);
                map.put(key, node);
                ptList(dm1);
                return;
            }
            ptList(dm1);
        }
        public int get(int key) {
            //无key
            if(!map.containsKey(key)){
                ptList(dm1);
                return -1;
            }
            //有key
            else{
                DoubleNode node = map.get(key);
                list_delByNode(node);
                list_addRight(node);
                //map不用动
                ptList(dm1);
                return node.val;
            }
        }

        //debug
        void ptList(DoubleNode node){
            while(node!=null){
                System.out.print(node.key+"-"+node.val+" ");
                node=node.next;
            }
            System.out.println();
        }
    }


    @Test
    public void test() {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(2, 1); // 缓存是 {1=1}
        lRUCache.put(1, 1); // 缓存是 {1=1, 2=2}
        lRUCache.put(2, 3); // 缓存是 {1=1, 2=2}
        lRUCache.put(4, 1); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get(1));
        System.out.println(lRUCache.get(2));
    }
}
